package leetcode_top;

import java.util.Arrays;

import org.junit.Test;

public class Ex28 {
    class Solution {
        //实现kmp算法
        public int strStr(String haystack, String needle) {
            int[] next = getNext(haystack);
            int s1 = 0, s2 = 0;
            while (s1 < haystack.length() && s2 < needle.length()) {
                if (haystack.charAt(s1) == needle.charAt(s2)) {
                    s1++;
                    s2++;
                } else {
                    if (next[s1] == -1) {
                        s1++; //已经无捷径可走
                        //跳出后，s2==0, 此时比较的是首位，若某次首位相同，进入第一个分支，s2才会产生阶跃
                    } else {
                        s2 = next[s2];//逻辑上移动
                    }
                }
            }
            return s2 == needle.length() ? s1 - s2 : -1;
        }

        public int[] getNext(String s) {
            int len = s.length();
            int[] next = new int[len];
            char[] cs = s.toCharArray();
            next[0] = -1;
            next[1] = 0;
            int last = 0;
            int idx = 2;
            while (idx < len) {
                if (cs[last] == cs[idx - 1]) {
                    next[idx++] = ++last;
                } else if (last > 0) {
                    last = next[last];
                } else {
                    next[idx++] = 0;
                }
            }
            return next;
        }
    }

    @Test
    public void test() {
        Solution s = new Solution();
        System.out.println(Arrays.toString(s.getNext("ababc")));        
    }
}
